package jzOffer;

import java.util.LinkedList;
import java.util.Queue;

public class Num13 {
    //BFS
    public int movingCount(int m, int n, int k) {
        boolean[][] vis=new boolean[m][n];
        Queue<int[]> q=new LinkedList<>();
        q.offer(new int[]{0,0,0,0});
        int count=0;
        while(q.size()>0){
            int[] x=q.poll();
            int i=x[0],j=x[1],si=x[2],sj=x[3];
            if(i>=m || j>=n || vis[i][j] || si+sj>k) continue;
            vis[i][j]=true;
            count++;
            q.offer(new int[]{i+1,j,(i+1)%10!=0?si+1:si-8,sj});
            q.offer(new int[]{i,j+1,si,(j+1)%10!=0?sj+1:sj-8});
        }
        return count;
    }



    //DFS
//    int m,n,k;
//    boolean[][] vis;
//    public int movingCount(int m, int n, int k) {
//        this.m=m;
//        this.n=n;
//        this.k=k;
//        vis=new boolean[m][n];
//        return dfs(0,0,0,0);
//
//    }
//    private int dfs(int i,int j,int si,int sj){
//        if(i>=m || j>=n || vis[i][j] ||si+sj>k) return 0;
//        vis[i][j]=true;
//        return 1+dfs(i+1,j,(i+1)%10!=0?si+1:si-8,sj)+dfs(i,j+1,si,(j+1)%10!=0?sj+1:sj-8);
//    }
}
